To decode a long genome sequence, shotgun sequencing is the state-of-the-art technique. It needs to properly sequence a very\nlarge number, sometimes as large as millions, of short partially readable strings (fragments). Arranging those fragments in correct\nsequence is known as fragment assembling, which is an NP-problem. Presently used methods require enormous computational\ncost. In this work, we have shown how our modified genetic algorithm (GA) could solve this problem efficiently. In the proposed\nGA, the length of the chromosome, which represents the volume of the search space, is reduced with advancing generations, and\nthereby improves search efficiency.We also introduced a greedy mutation, by swapping nearby fragments using some heuristics, to\nimprove the fitness of chromosomes.We compared results with Parsons� algorithm which is based on GA too. We used fragments\nwith partial reads on both sides, mimicking fragments in real genome assembling process. In Parsons� work base-pair array of the\nwhole fragment is known. Even then, we could obtain much better results, and we succeeded in restructuring contigs covering\n100% of the genome sequences.
Loading....